package 算法;

public class 最大回文子符串 {
    public static void main(String[] args) {
        new Solution2().longestPalindrome("sasdf");
    }
}
class Solution2 {
    public String longestPalindrome(String s) {
       int len = s.length();

       boolean[][] dp = new boolean[len][len];
       for (int i = 0;i<len;i++){
           dp[i][i] = true;
       }
       int max = 1;
       int index = 0;
       for (int i = 1; i < len; i++){
           for (int j = 0; j < i; j++){
               if(s.charAt(i) == s.charAt(j) && dp[j+1][i-1]){
                    dp[i][j] = true;
                    if(j-i+1 > max){
                        max = j-i+1;
                        index = i;
                    }
               }
           }
       }

       return s.substring(index,index+max);
    }
}